package com.clstu.linkedlist;

/**
 * 演示双向链表的模拟和实现
 * 双向链表对于单链表的优点 1.可以从后向前查找
 *                     2.可以自我删除.
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        //测试是否写对
        //创建双向链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        //创建一些节点数据
        HeroNode1 hn1 = new HeroNode1(2, "along", "龙王");
        HeroNode1 hn2 = new HeroNode1(8, "jack", "夹克");
        HeroNode1 hn3 = new HeroNode1(9, "mary", "嫁给我");
        HeroNode1 hn4 = new HeroNode1(6, "smith", "神秘人");
        HeroNode1 hn5 = new HeroNode1(1, "alice", "密码学老大");
        //排序插入是否正确
        doubleLinkedList.addByOrder(hn1);
        doubleLinkedList.addByOrder(hn2);
        doubleLinkedList.addByOrder(hn3);
        doubleLinkedList.addByOrder(hn4);
        doubleLinkedList.addByOrder(hn5);
        System.out.println("修改前");
        doubleLinkedList.list();
        //删除
        doubleLinkedList.delete(1);
        doubleLinkedList.delete(9);
        //修改
        doubleLinkedList.update(new HeroNode(2,"along","龙少"));
        //查看内容
        System.out.println("修改后");
        doubleLinkedList.list();

    }
}
/**
 * heroNode1 一个对象就是一个节点(双向链表版本的)
 */
class HeroNode1{
    public int id;//编号
    public String name;//姓名
    public String nickName;//别名
    public HeroNode1 next;//next,指向后一个节点
    public HeroNode1 pre;//pre,指向前一个节点

    //构造器
    public HeroNode1(int id, String name, String nickName) {
        this.id = id;
        this.name = name;
        this.nickName = nickName;
    }

    //为了显示方便,重写toString方法
    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\''+
                '}';
    }
}

/**
 * 链表类,管理HeroNode
 */
class DoubleLinkedList {
    //先初始化一个头节点,头节点不要动,不保存数据,只用于引用.
    private HeroNode1 head = new HeroNode1(0,"","");

    public HeroNode1 getHead() {
        return head;
    }

    //编写方法添加节点(不排序)
    public void add(HeroNode1 heroNode){
        //1.找到尾节点
        HeroNode1 tmp = head;//tmp便于遍历,头节点不能动
        while (true){
            //如果找到最后
            if(tmp.next == null){
                break;
            }
            //后移遍历链表
            tmp = tmp.next;
        }
        //循环结束后tmp就是最后一个节点了
        //2.将节点插入到最后即可
        tmp.next = heroNode;
        heroNode.pre =tmp;
    }

    //编写方法排序添加,如果编号存在则不能添加
    public void addByOrder(HeroNode1 heroNode){
        //1.找到插入的位置
        HeroNode1 tmp = head;
        while (true){
            //如果遍历完
            if(tmp.next == null){
                break;
            }
            //如果找到合适位置
            if(tmp.next.id > heroNode.id){
                break;
            }
            //如果不能添加
            if(tmp.next.id == heroNode.id){//如果要用next.id判断就保存同一都用这个判断
                System.out.println("编号已经存在,不能添加,失败");
                return;
            }
            //后移
            tmp = tmp.next;
        }
        //循环结束一定是可以插入的位置
        //2.插入(需要判断是否是插入到最后一个)
        if(tmp.next != null) {
            //不是最后一个才需要连接后一个节点的指针
            heroNode.next = tmp.next;
            heroNode.next.pre = heroNode;
        }
        tmp.next = heroNode;
        heroNode.pre = tmp;
    }

    //编写方法显示整个链表
    public void list(){
        //判断链表是否空
        if(head.next==null){
            System.out.println("链表空,无数据");
            return;
        }
        //循环遍历显示整个链表即可
        HeroNode1 tmp = head.next;//头节点不能动,于是用临时变量来遍历
        while (true){
            //如果到最后了
            if(tmp == null) return;
            //显示节点信息
            System.out.println(tmp);
            //后移
            tmp = tmp.next;
        }
    }

    //编写方法修改链表的信息(根据编号)
    public void update(HeroNode heroNode){
        //判断链表是否空
        if(head.next==null) {
            System.out.println("链表空,修改失败");
            return;
        }
        //1.找到修改的位置
        HeroNode1 tmp = head.next;//头节点不能动,用临时变量来遍历
        boolean find = false;//用于判断是否找到
        while (true){
            //如果遍历完(避免空指针异常需要先判断,注意!!!)
            if(tmp == null){
                break;
            }
            //如果找到
            if (heroNode.id == tmp.id){
                find=true;
                break;
            }
            //后移
            tmp = tmp.next;
        }
        //判断是否找到
        if(find){
            //修改信息
            tmp.name = heroNode.name;
            tmp.nickName = heroNode.nickName;
        }else {
            //没找到
            System.out.println("没有找到编号信息,修改失败");
        }
    }

    //编写方法删除节点,根据id(注意,跟单链表不同的是,双链表可以自我删除,就是直接找到待删除的节点,而不是它的前一个)
    public void delete(int id){
        //判断链表是否空
        if (head.next==null){
            System.out.println("链表空,删除失败");
            return;
        }
        //1.找到删除的位置
        HeroNode1 tmp = head.next;
        boolean find = false;//是否找到
        while (true){
            //如果遍历完
            if(tmp ==null){
                break;
            }
            //如果找到
            if(id == tmp.id){
                find = true;
                break;
            }
            //后移
            tmp=tmp.next;
        }
        //判断是否找到
        if (find){
            //如果找到
            //被删除的节点(tmp)将在没有变量指向它,会被垃圾回收机制自动回收
            tmp.pre.next = tmp.next;
            //需要注意 这句话有可能会有空指针异常,当删除的节点是最后一个的时候所以加个if判断一下
            if (tmp.next != null) {
                tmp.next.pre = tmp.pre;
            }
        }else {
            System.out.println("未找到改编号,删除失败");
        }
    }

}